// 力扣97. 交错字符串
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();
        if (n + m != t) {
            return false;
        }
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                int p = i + j - 1;
                if (i > 0) {
                    dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }
        return dp[n][m];
    }
}



// 力扣221. 最大正方形
class Solution1 {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int maxSide = 0;
        int[] dp = new int[n + 1];
        int prev = 0; // 保存左上角的值

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int temp = dp[j + 1]; // 保存当前值，用于下一轮计算
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[j + 1] = 1;
                    } else {
                        dp[j + 1] = Math.min(Math.min(dp[j], dp[j + 1]), prev) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[j + 1]);
                } else {
                    dp[j + 1] = 0;
                }
                prev = temp; // 更新prev为当前列的旧值
            }
        }

        return maxSide * maxSide;
    }
}